As computing and networking devices become faster, the requirement for speed in the management of data tables challenges conventional approaches. The speed of a key search, for example, in which data associated with a key must be found in a table quickly, has become a critical issue, and sometimes a bottleneck, in many devices and applications. A key may be any piece of data used as an index or search criterion for finding additional data, but in a networking context, keys are typically Internet protocol (IP) addresses, media access control (MAC) addresses, virtual local area network (VLAN) tags, and other network identifiers.
Solutions that accelerate key search speed sometimes depend on the characteristics of the memory used to store the data table being searched. Random access memory (RAM) stores data at a particular location denoted by an address. When the address is supplied to the RAM, the RAM returns the data stored there. To find the correct address, however, either an index of all the keys needs to be sorted and searched for an address associated with the key or all the associated data entries must be searched for a representation of the key and its associated RAM address. There are many algorithms that seek to shorten the search time for an address associated with a key.
One type of hardware memory, content addressable memory (CAM), accelerates the search for a stored data item by retrieving the data based on the content of the data itself, rather than on its address in memory. When data is supplied to a CAM, the CAM directly returns an address where the associated data is found. For many applications, CAM provides better performance than conventional memory search algorithms by comparing desired information against an entire list of stored data entries simultaneously. Hence, CAM is used in applications in which search time is an important issue and must be constrained to very short durations.
Unfortunately, both discrete hardware and integrated circuit CAM implementations can be relatively expensive both in chip area requirements and/or design complexity. In some applications a direct-mapped cache could be used as a substitute for a CAM, but the fully associative characteristic of a CAM—where a data entry can be placed anywhere in the data structure—is lost and undesirable characteristics such as data collisions and unused memory locations are introduced.